#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

string h[10] = { "", "" , "abc" , "def" , "ghi" , "jkl" , "mno" , "pqrs" , "tuv" , "wxyz" };
vector<string> ret;
string path;

void dfs(string digits, int pos)
{
    if (pos == digits.size())
    {
        ret.push_back(path);
        return;
    }

    for (auto c : h[digits[pos] - '0'])
    {
        path.push_back(c);
        dfs(digits, pos + 1);
        path.pop_back();
    }
}

vector<string> letterCombinations(string digits) {
    if (digits.size() == 0)
        return ret;

    dfs(digits, 0);
    return ret;
}



int main()
{
	return 0;
}